#pragma once
#include"BinaryTree.h"
#include"queue.h"
//前序遍历
void PreOrder(TreeNode* root)
{
    if(root == NULL)
        return ;
    printf("%c ",root->val);
    PreOrder(root->left);
    PreOrder(root->right);
}
//中序遍历
void InOrder(TreeNode* root)
{
    if(root == NULL)
        return ;
    InOrder(root->left);
    printf("%c ",root->val);
    InOrder(root->right);
}
//后序遍历
void PostOrder(TreeNode* root)
{
    if(root == NULL)
        return ;
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%c ",root->val);
}
//层序遍历
void LevelOrder(TreeNode* root)
{
   if(root == NULL)
      return ;
    queue q;
    Init(&q);
    push(&q,root);
    while(!empty(&q))
    {
      TreeNode* tmp = front(&q);
      printf("%c ",tmp->val);
      if(tmp->left)
        push(&q,tmp->left);
      if(tmp->right)
        push(&q,tmp->right);
      pop(&q);
    }
    printf("\n");
    Destory(&q);
}
//判断是否是完全二叉树
bool BinaryTreeComplete(TreeNode* root)
{
  if(root == NULL)
    return true;
  queue q;
  Init(&q);
  push(&q,root);
  while(!empty(&q))
  {
    TreeNode* tmp = front(&q);
    if(tmp == NULL) break;
    push(&q,tmp->left);
    push(&q,tmp->right);
    pop(&q);
  }
  //判断后序是否都是空节点,如果是就是完全二叉树，否则不是
  bool flag = true;
  while(!empty(&q))
  {
    TreeNode* tmp = front(&q);
    if(tmp != NULL)
    {
      flag = false;//不能直接return  后序还要销毁队列
      break;
    }
    pop(&q);
  }
  Destory(&q);
  return flag;
}
//二叉树的销毁
void BinaryTreeDestory(TreeNode* root) //由于是传值，所以在外部还需要把root指针置空！防止其为野指针
{
  if(root == NULL)
    return ;
  //才用后序的方式销毁，因为如果先销毁根节点，那么后序就找到其左右节点了
  BinaryTreeDestory(root->left);
  BinaryTreeDestory(root->right);
  free(root);
  root = NULL;
}
//二叉树叶子结点个数
int  BinaryTreeLeafSize(TreeNode* root)
{
  if(root == NULL)
    return 0;
  //叶子节点:左右指针都是空
  if(root->left == NULL && root->right == NULL)
    return 1;
  //根节点的叶子节点个数 = 左子树的叶子节点个数+右子树的叶子节点个数
  return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
//二叉树结点个数
int  BinaryTreeSize(TreeNode* root)
{
  if(root == NULL)
    return 0;
  //节点个数 = 当前节点 + 左右子树的节点个数
  return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
//求第K层结点个数
int BinaryTreeLevelSize(TreeNode* root, int k)
{
  //规定根节点所在的层数为第一层
  if(root == NULL || k <= 0)
    return 0;
  if(k == 1) //到达最底层了
    return 1;
  //当前第k层的节点个数 = 左右子树第k-1层节点个数之和
  return BinaryTreeLevelSize(root->left,k-1)+BinaryTreeLevelSize(root->right,k-1);
}
//二叉树的高度/深度
int BinaryTreeDepth(TreeNode* root)
{
  //二叉树的高度 = max(左子树的高度,右子树的高度)+1
  if(root == NULL)
    return 0;
  int leftDepth = BinaryTreeDepth(root->left);
  int rightDepth = BinaryTreeDepth(root->right);
  return leftDepth>rightDepth?leftDepth+1:rightDepth+1;
}
//查找值为x的结点
//TreeNode* BinaryTreeFind(TreeNode* root, BTDataType x) //err写法 ->不是任何路径都有返回值
//{
//  if(root == NULL || root->val == x) 
//    return root;
//  BinaryTreeFind(root->left,x);
//  BinaryTreeFind(root->right,x);
//}
TreeNode* BinaryTreeFind(TreeNode* root, BTDataType x)
{
  	if (root == NULL)
		return NULL;
	//思路： 先判断根的值是不是x 不是的话 去左子树找  左子树找不到再去右子树找 (类似前序遍历)
	if (root->val == x)
		return root;
  //先去左树寻找,找到了就直接返回,没有再去右树找,找不到就返回NULL 
  TreeNode* leftAns = BinaryTreeFind(root->left,x);
  if(leftAns) return leftAns;
  TreeNode* rightAns = BinaryTreeFind(root->right,x);
  if(rightAns) return rightAns;
  return NULL;
}
